Linux Cubed Series 3: Developer Tools/Linux Cubed Series 3 - Developer Tools.iso/devel/lang/c/c-tools-.000/c-tools-/c-tools-0.4/hash.c

C/C++ Source or Header | 1995-08-13 | 4.3 KB | 210 lines

/* hash.c -- General hash table handling functions.
   Copyright (C) 1995 Sandro Sigala - <[e-mail]> */

/* $Id: hash.c,v 1.5 1995/08/08 11:52:03 sandro Exp $ */

/* This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */


/*
 *  to do:
 *   - table must be allocated on hash_table_build(size) call with
 *     an user preferred size.
 *   - an user made hashing function can be specified by the user.
 *
 *  return codes:
 *    HASH_OK: all ok
 *    HASH_INVALID_PARAMETER: invalid parameter(s)
 *    HASH_NOT_FOUND: key not found in hash table
 *    HASH_ALREADY_EXIST: key already exists in hash table
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hash.h"
#include "misc.h"

static struct bucket *
build_bucket (char *key)
{
    struct bucket *ptr;

    ptr = (struct bucket *) xmalloc (sizeof (struct bucket));

    ptr->key = (char *) xmalloc (strlen (key) + 1);
    strcpy (ptr->key, key);

    ptr->data = NULL;
    ptr->next = NULL;

    return ptr;
}

static void
free_bucket (struct bucket *ptr)
{
    assert (ptr != NULL);

    if (ptr->key != NULL)
    free (ptr->key);
    if (ptr->data != NULL)
    free (ptr->data);

    free (ptr);
}

struct hash_table *
hash_table_build (void)
{
    struct hash_table *ptr;
    int i;

    ptr = (struct hash_table *) xmalloc (sizeof (struct hash_table));

    for (i = 0; i < HASH_TABLE_SIZE; i++)
    ptr->table[i] = NULL;

    return ptr;
}

int
hash_table_free (struct hash_table *table)
{
    struct bucket *bucket, *next;
    int i;

    if (table == NULL)
    return HASH_INVALID_PARAMETER;

    for (i = 0; i < HASH_TABLE_SIZE; i++)
    {
    bucket = table->table[i];

    while (bucket != NULL)
    {
        next = bucket->next;
        free_bucket (bucket);
        bucket = next;
    }
    }

    free (table);

    return HASH_OK;
}

static unsigned int
hash_table_hash (char *key)
{
    unsigned int hash = 0;
    char *p;

    for (p = key; *p != '\0'; p++)
    hash = hash * 58 + *p;

    return (hash % HASH_TABLE_SIZE);
}

int
hash_table_add (struct hash_table *table, char *key)
{
    struct bucket *bucket;
    int hash;

    if (table == NULL || key == NULL)
    return HASH_INVALID_PARAMETER;

    if (hash_table_lookup (table, key) == HASH_OK)
    return HASH_ALREADY_EXIST;

    hash = hash_table_hash (key);

    if (table->table[hash] == NULL)
    table->table[hash] = build_bucket (key);
    else
    {
    bucket = table->table[hash];

    while (bucket->next != NULL)
        bucket = bucket->next;

    bucket->next = build_bucket (key);
    }

    return HASH_OK;
}

int
hash_table_lookup (struct hash_table *table, char *key)
{
    struct bucket *bucket;
    int hash;

    if (table == NULL || key == NULL)
    return HASH_INVALID_PARAMETER;

    hash = hash_table_hash (key);

    for (bucket = table->table[hash]; bucket != NULL; bucket = bucket->next)
    if (strcmp (bucket->key, key) == 0)
        return HASH_OK;

    return HASH_NOT_FOUND;
}

int
hash_table_set_data (struct hash_table *table, char *key, void *data)
{
    struct bucket *bucket;
    int hash;

    if (table == NULL || key == NULL || data == NULL)
    return HASH_INVALID_PARAMETER;

    hash = hash_table_hash (key);

    for (bucket = table->table[hash]; bucket != NULL; bucket = bucket->next)
    if (strcmp (bucket->key, key) == 0)
    {
        bucket->data = data;
        return HASH_OK;
    }

    return HASH_NOT_FOUND;
}

void *
hash_table_retrive_data (struct hash_table *table, char *key)
{
    struct bucket *bucket;
    int hash;

    if (table == NULL || key == NULL)
    return NULL;

    hash = hash_table_hash (key);

    for (bucket = table->table[hash]; bucket != NULL; bucket = bucket->next)
    if (strcmp (bucket->key, key) == 0)
        return bucket->data;

    return NULL;
}

/* hash.c ends here */